package com.jiang.daily.Q3097;

/**
 * @author Jiang
 * @version 1.0
 * @date 2025/01/17 0:22
 */
class Solution {
    // 滑动窗口
    public int minimumSubarrayLength(int[] nums, int k) {
        int n = nums.length;
        int[] bits = new int[30]; // 记录对应比特位上出现的次数
        int res = Integer.MAX_VALUE;
        for (int left = 0, right = 0; right < n; right++) { // left ~ right 表示窗口大小
            for (int i = 0; i < 30; i++) { // 记录right的比特位
                bits[i] += (nums[right] >> i) & 1;
            }
            while (left <= right && cal(bits) >= k) { // 窗口大于等于0并且窗口中所有元素或运算大于等于k，缩小窗口
                res = Math.min(res, right - left + 1); // 记录窗口(子数组)或运算能大于等于的最小长度
                // 缩小窗口，减去left的比特位
                for (int i = 0; i < 30; i++) {
                    bits[i] -= (nums[left] >> i) & 1;
                }
                left++; // left += 1
            }
        }
        return res == Integer.MAX_VALUE ? -1 : res;
    }
    // 计算窗口中元素或运算的值
    private int cal(int[] bits) {
        int res = 0;
        for (int i = 0; i < bits.length; i++) {
            if (bits[i] > 0) { // bits[i] 只要大于0，那么记录到res中
                res |= 1 << i; // 1 << i 记录到对应的比特位上
            }
        }
        return res;
    }
}
